package 力扣;

/**
 示例:

 board =
 [
 ['A','B','C','E'],
 ['S','F','C','S'],
 ['A','D','E','E']
 ]

 给定 word = "ABCCED", 返回 true
 给定 word = "SEE", 返回 true
 给定 word = "ABCB", 返回 false
 */
public class _79单词搜索 {
    int[][] direction ={{0,1},{1,0},{0,-1},{-1,0}};
    boolean[][] visited ;
    public boolean exist(char[][] board, String word) {
            int m = board.length;
            int n = board[0].length;
            visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if( dfs(0,i,j,word,board)) return true;
            }
        }

        return false;
    }

    private boolean dfs(int start, int i, int j, String word, char[][] board) {
        if( start == word.length() ){
            return true;
        }
        if( i> board.length || i< 0 || j > board[0].length || j < 0|| word.charAt(start) != board[i][j] || visited[i][j]) return false;
        visited[i][j] = true;
        for (int k = 0; k < direction.length; k++) {
            if( dfs(start+1,i+direction[k][0],j+direction[k][1],word,board)) return true;
            visited[i][j] = false;
        }
        return false;
    }
}
